package t_1181

//* Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func diameterOfBinaryTree(root *TreeNode) int {
	if root == nil {
		return 0
	}
	diameter := 0
	return max(diameter, depth(&diameter, root.Left)+depth(&diameter, root.Right))
}

func depth(diameter *int, node *TreeNode) int {
	if node == nil {
		return 0
	}
	leftH, rightH := depth(diameter, node.Left), depth(diameter, node.Right)
	*diameter = max(*diameter, leftH+rightH)
	return max(leftH, rightH) + 1
}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func Bfs(root *TreeNode) int {
	res := 0

	s := make([]*TreeNode, 1)
	if root == nil {
		return 0
	}

	s[0] = root
	for s != nil {
		temp := make([]*TreeNode, 0)
		cp := 0
		for _, v := range s {

			res++
			if len(s) != 1 {
				res++
			}

			if v.Left != nil {
				temp = append(temp, v.Left)
			}
			if v.Right != nil {
				temp = append(temp, v.Right)
			}
			cp++
		}
		if cp == 0 {
			s = nil
		} else {
			s = temp
		}
	}

	return res
}
